import java.util.*;

/**
 * @author yu
 * @date 2025/6/3 22:09
 * @description: 40. 组合总和 II
 * 
 */
public class _07_backtracking_06_40 {
    public static LinkedList<Integer> path = new LinkedList<>();
    public static List<List<Integer>> ans = new ArrayList<>();
    public static boolean[] used;
    static int sum = 0;

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        // 加标志数组，用来辅助判断同层节点是否已经遍历
        Arrays.fill(used, false);
        // 为了将重复的数字都放到一起，所以先进行排序
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return ans;
    }

    private static void backTracking(int[] candidates, int target, int startIndex) {
        if (sum  > target)  return;

        if (sum == target)  ans.add(new ArrayList(path));

        for (int i = startIndex; i < candidates.length; i++) {
            // 树层减枝  (出现重复节点，同层的第一个节点已经被访问过，所以直接跳过)
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            sum += candidates[i];
            path.add(candidates[i]);
            // 每个节点仅能选择一次，所以从下一位开始
            backTracking(candidates, target, i + 1);
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String[] input = scanner.nextLine().split(" ");
        int[] candidates = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            candidates[i] = Integer.parseInt(input[i].trim());
        }

        int target = scanner.nextInt();

        // 计算结果
        List<List<Integer>> result = combinationSum2(candidates, target);

        System.out.println(result);


    }
}
